package 数组和链表.linklist;

import 抽象数据类型.DListNode;
import 抽象数据类型.ListNode;

public class DLinkedList  {
    private DListNode first = new DListNode();
    private int length;


    public DLinkedList() {

    }
    //构造循环链表

    public DLinkedList CircularLinkedListHead() {
        DListNode headNode = first;
        if (first.next != null) {
            DListNode currentNode = headNode.next;
            while (currentNode.next != null) {
                currentNode = currentNode.next;
            }
            currentNode.next = headNode.next;
        }
        return new DLinkedList(headNode, length);
    }

    public DLinkedList CircularLinkedListTail() {
        DListNode headNode = first;
        if (first.next != null) {
            DListNode currentNode = headNode.next;
            while (currentNode.next != null) {
                currentNode = currentNode.next;
            }
            currentNode.next = headNode.next;
            headNode.next = currentNode;
        }
        return new DLinkedList(headNode, length);
    }

    public DLinkedList(DListNode first, int length) {
        this.first = first;
        this.length = length;
    }

   
    public DLinkedList InitList(Object[] L) {
        for (Object o : L) {
            ListInsert(o, length);
        }
        return new DLinkedList(first, length);
    }

   
    public void DestroyList() {
        first = null;
    }

   
    public boolean ListEmpty() {
        if (first.next == null) {
            return true;
        }
        return false;
    }

   
    public int ListLength() {
        int count = 0;
        DListNode current = first.next;
        while (current != null) {
            current = current.next;
            count++;
        }
        return count;
    }

   
    public Object GetElem(int i) {
        if (i < 0 || i >= this.length) {
            throw new IndexOutOfBoundsException("下表越界");
        }
        int index = 0;
        DListNode current = first.next;
        while (true) {
            if (index == i) {
                return current;
            }
            current = current.next;
            index++;
        }
    }

   
    public int LocateElem(Object e) {
        DListNode current = first.next;
        int index = 0;
        while (current != null) {
            if (current.getVal() == (int) e) {
                return index;
            }
            current = current.next;
            index++;
        }
        return 0;
    }

   
    public Object PirorElem(Object e) {
        DListNode current = first.next;
        int index = 0;
        while (current != null) {
            if (current.getVal() == (int) e && index != 0) {
                return current.pre;
            }
            current = current.next;
            index++;
        }
        return null;
    }

   
    public Object nextElem(Object e) {
        DListNode current = first.next;
        while (current != null) {
            if (current.getVal() == (int) e) {
                if (current.next != null) {
                    return current.next;
                }
            }
            current = current.next;

        }
        return null;
    }

   
    public void ListInsert(Object e, int i) {
        if (i < 0 || i > length) {
            throw new IndexOutOfBoundsException("数组越界");
        }

        int index = 0;
        DListNode current = first.next;
        DListNode insertNode = new DListNode((int) e);
        if (current == null) {

            first.next = insertNode;
            insertNode.pre = first;
        } else {

            while (current.next != null) {
                ListNode temp = null;
                if (index == i) {
                    current.pre.next = insertNode;
                    insertNode.next = current;
                    insertNode.pre = current.pre;
                    current.pre = insertNode;
                    return;
                }

                current = current.next;
                index++;
            }
            if (current.next == null) {
                current.next = insertNode;
                insertNode.pre = current;
            }
        }
        this.length++;
    }

   
    public Object ListDelete(int i) {

        if (i < 0 || i >= length) {
            throw new IndexOutOfBoundsException("数组越界");
        }
        int index = 0;
        DListNode current = first.next;
        while (current != null) {
            if (index == i) {
                if (current.next != null) {
                    current.pre.next = current.next;
                    current.next.pre = current.pre;
                } else {
                    current.pre.next = null;
                }
            }
            current = current.next;
            index++;
        }

        this.length--;
        return current;
    }

   
    public void ListObjectraverse() {
        int count = 40;
        DListNode current = first.next;
        DListNode tailHead = null;
        while (current != null && count >= 0) {
            count--;
            System.out.print(current.getVal() + "\t");
            tailHead = current;
            current = current.next;
        }
        System.out.println();
        current = tailHead;
        while (current != null) {
            System.out.print(current.getVal() + "\t");
            current = current.pre;
        }
    }

   
    public void Replace(Object e, int i) {
        DListNode current = first.next;
        int index = 0;
        while (current != null) {
            if (index == i) {
                current.setVal((int) e);
            }
            current = current.next;
            index++;
        }
    }

    static class MainTest {
        public static void main(String[] args) {
            Object[] a = {1, 3, 4, 5, 9};
            Object[] b = {2, 4, 6, 10};
            DLinkedList AL = (DLinkedList) (new DLinkedList()).InitList(a);
            DLinkedList BL = (DLinkedList) (new DLinkedList()).InitList(b);
           /* LinkedList circularLinkedListHead = AL.CircularLinkedListHead();

            circularLinkedListHead.ListObjectraverse();*/
            AL.ListObjectraverse();
            System.out.println();
            AL.ListDelete(4);
            AL.ListObjectraverse();
          /*  DLinkedList circularLinkedListTailAl = AL.CircularLinkedListTail();
            DLinkedList circularLinkedListTailBl = BL.CircularLinkedListTail();
            circularLinkedListTailAl.ListObjectraverse();
            System.out.println();
            MergeListTail(circularLinkedListTailAl, circularLinkedListTailBl).ListObjectraverse();*/
        }

        private static DLinkedList MergeListTail(DLinkedList La, DLinkedList Lb) {
            DListNode LaDListNode = La.first;
            DListNode LbDListNode = Lb.first;
            DListNode LaTailNode = LaDListNode.next;
            DListNode LbTailNode = LbDListNode.next;
            DListNode tempAHead = LaTailNode.next;//头节点
            LaTailNode.next = LbTailNode.next;
            LbTailNode.next = tempAHead;
            La.first = Lb.first;
            return La;

        }
    }

    static class Main {
        public static void main(String[] args) {
            Object[] a = {1, 3, 4, 5, 9};
            Object[] b = {2, 4, 6, 10};
            DLinkedList AL = (DLinkedList) (new DLinkedList()).InitList(a);
            DLinkedList BL = (DLinkedList) (new DLinkedList()).InitList(b);
            AL.ListObjectraverse();
            System.out.println();
            BL.ListObjectraverse();
            /*AL.ListInsert(1, 0);
            System.out.println();
            System.out.println(AL.length);
            AL.ListDelete(4);
            AL.ListObjectraverse();*/
            System.out.println();
            MergerListOne((AL), BL).ListObjectraverse();
        }


        private static DLinkedList MergerList(DLinkedList La, DLinkedList Lb) {
            DLinkedList Lc = new DLinkedList();
            DListNode currentC = Lc.first;
            DListNode currentA = La.first.next;
            DListNode currentB = Lb.first.next;
            while (currentA != null && currentB != null) {
                if (currentA.getVal() <= currentB.getVal()) {
                    currentC.next = currentA;
                    currentA = currentA.next;
                } else {
                    currentC.next = currentB;
                    currentB = currentB.next;
                }
                currentC = currentC.next;
            }
            return Lc;
        }

        private static DLinkedList MergerListOne(DLinkedList La, DLinkedList Lb) {
            DListNode currentA = La.first.next;
            DListNode currentB = Lb.first.next;
            DListNode prior = La.first;
            while (currentA != null && currentB != null) {
                if (currentA.getVal() >= currentB.getVal()) {
                    DListNode insertNode = new DListNode(currentB.getVal());
                    prior.next = insertNode;
                    insertNode.next = currentA;
                    currentB = currentB.next;
                } else {
                    currentA = currentA.next;
                }
                prior = prior.next;
            }
            if (currentB != null) {
                prior.next = currentB;
            }
            return La;
        }

    }
}
